In short, the general interactive configuration problem can be described as having a computer based model of a number of selectable objects, or selectable attributes of objects, and a number of rules that define constraints on the selectable objects and attributes. The configuration process is the process of selecting or deselecting objects or object attributes until a solution is found that satisfies all the constraints. During this configuration, the configuration engine will deduce consequences of the selections made, as well as interactively handling conflicting selections, and aiding the user in resolving these.
Traditionally, the configuration process in a client/server environment consisted in the user making a number of selections at the client side and then submitting the selections for validation by the server. This traditional way of operation has the serious drawback, that the user can end up with a set of selections that does not satisfy all the constraints, without having means of knowing exactly which selections caused the inconsistency. It may be likely that the user is forced to undo all selections in order to reach a valid state.
A computer system intended to solve a configuration problem is a special application of artificial intelligence where the problem can be stated in terms of a set of selectable elements and a number of relations between these selectable elements. The configuration problem is solved when the set of all selectable elements is completely divided into two disjunct sub-sets representing elements that are included in the configuration and elements that are excluded from the configuration, respectively, without violating any of the relations between the selectable elements.
A selectable element is anything that can be included or excluded. It can be a physical object (e.g. a car or a specific kind of engine), an attribute (e.g. the color red or the texture pattern of a carpet) or something abstract (e.g. a specific number of trips between home and work or a particular type of contract).
A relation is a rule involving one or more selectable elements. The purpose of a rule is to constrain the selection of elements to obey some requirements. A rule can be based on a physical limitation (e.g. if a car needs a large engine to support a large number of selected electrical accessories), or a discretionary decision (e.g. if management decides that all cars having a particular large engine are produced only in red color to give them a more sporty look). Often the term "constraint" is used to refer to a rule limiting how elements can be combined.
A configuration engine is the heart of a computer system for solving configuration problems. The configuration engine maintains a value for each selectable element reflecting the current knowledge of that element. The knowledge value is "unknown" to begin with, and can be set by either the user of the computer system or the configuration engine. Some examples of values are:
Selected, meaning that the user operating the computer system has chosen to positively include the element.
Discarded, meaning that the user operating the computer system has chosen to positively exclude the element.
Concluded, meaning that the Configuration Engine has deduced that the element must be included.
Rejected, meaning that the Configuration Engine has deduced that the element must be excluded.
Unbound, meaning that the Configuration Engine has deduced that the element may be either included or excluded.
Possibly concluded, meaning that the Configuration Engine has deduced that the element may be included but cannot be excluded.
Possibly rejected, meaning that the Configuration Engine has deduced that he element may be excluded but cannot be included.
Unknown, meaning that the configuration engine has no present knowledge of whether the element is included or not.
It is possible to define a partial ordering of knowledge values that reflects the level of knowledge which the configuration engine has about the element. An example of such an ordering is given in table 1 below:
TABLE 1 ______________________________________ Level Knowledge Value ______________________________________ 3 Selected, Discarded, Concluded, Rejected 2 Unbound 1 Possibly concluded, Possibly rejected 0 Unknown ______________________________________
Table 1 shows the ordering of knowledge values.
Two values are said to be equivalent if they have the same effect on the set of selected elements. Using the example values in table 1, selected is equivalent with concluded and discarded is equivalent with rejected.
If two different values of the same element are compared, one value may overrule the other value if it has a higher associated knowledge level. If e.g. the value of an element is "unbound" in one part of the computer system and "selected" in another part of the system, then the value of "selected" may overrule the value of "unbound".
An element is defined as "free" if it is either unbound, possibly concluded, possibly rejected or unknown.
An element is defined as "bound" if it is selected, discarded, concluded or rejected.
The configuration engine uses the rules to assist the user in the selection process. This assistance can be more thorough, the more calculations the configuration engine is allowed to perform. It is possible to define the amount of assistance given to the user in terms of the deduction level reached by computations of the configuration engine. Some possible definitions of deduction levels are given below:
Validation is defined as the deduction level where all rules have been examined without finding any violations.
Propagation is defined as the deduction level where the first implications of the rules are computed. If e.g. a rule states "if A then B" and A is included (selected), propagation means that the configuration engine has deduced that B is also included (selected).
A deduction of consequences is a calculation by the configuration engine where at least the propagation level is reached.
A contradiction is defined as the situation where the user performs a choice to either include or exclude an element, following which the configuration engine is not able to reach a level of validation because at least one rule is violated.